﻿#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <random>

using namespace std;

const int BOARD_SIZE = 9;
int cnt[512], num[261];//二进制数中含有1的个数(各个状态中可选择的数的个数)	lowbit对应的hash

// 函数声明
bool solvePuzzles(string inputFilePath);
//void printBoard(vector<vector<int>>& board);
void writeBoardToFile(vector<vector<int>>& board, const string& filePath);
void generatePuzzles(int numGames, int difficulty, int min_numEmptyCells, int max_numEmptyCells, bool uniqueSolution);
void generateFinalBoards(int numBoards);

int main(int argc, char* argv[]) {
	srand(static_cast<unsigned>(time(0)));

	for (int i = 0; i < (1 << BOARD_SIZE); ++i) {
		//i的二进制数中含有1的个数 即各个状态中可选择的数的个数
		//预处理降低时间复杂度
		//e.g:cnt[100010001(二进制数)] = 3
		for (int j = i; j; j -= j & (-j)) {
			++cnt[i];
		}
	}
	for (int i = 0; i < BOARD_SIZE; ++i) {
		//lowbit(1 << i)的hash,能找出lowbit(1 << i)所对应的第一个1的位置 
		num[1 << i] = i;
	}

	unordered_map<string, string> options;
	for (int i = 1; i < argc; i++) {
		if (string(argv[i]) == "-u")
			options[string(argv[i])] = string("");
		else if (string(argv[i])[0] == '-' && i + 1 < argc)
			options[string(argv[i])] = string(argv[i + 1]);
	}

	if (options.empty()) {
		cout << "参数不足，请参考示例输入！" << endl;
		return 1;
	}

	if (options.count("-c")) {
		int numFinalBoards = stoi(options["-c"]);
		if (numFinalBoards < 1 || numFinalBoards > 1000000) {
			cout << "数独终盘的数量应在1到1000000之间！" << endl;
			return 1;
		}

		generateFinalBoards(numFinalBoards);
		cout << numFinalBoards << " 个数独终盘已生成至finalboards.txt！" << endl;
	}
	else if (options.count("-s")) {
		string filePath = options["-s"];
		solvePuzzles(filePath);
		cout << "数独游戏解答已生成到 solution.txt 中！" << endl;
	}
	else if (options.count("-n")) {
		int numGames = stoi(options["-n"]);
		if (numGames < 1 || numGames > 10000) {
			cout << "数独游戏的数量应在1到10000之间！" << endl;
			return 1;
		}

		int difficulty = 1;
		int minEmptyCells = 20;
		int maxEmptyCells = 55;
		bool unique = false;

		if (options.count("-m")) {
			difficulty = stoi(options["-m"]);
			if (difficulty < 1 || difficulty > 3) {
				cout << "游戏难度应在1到3之间！" << endl;
				return 1;
			}
		}

		if (options.count("-r")) {
			string rangeStr = options["-r"];
			size_t separatorPos = rangeStr.find("~");
			if (separatorPos == string::npos) {
				cout << "无效的挖空数量范围！" << endl;
				return 1;
			}

			minEmptyCells = stoi(rangeStr.substr(0, separatorPos));
			maxEmptyCells = stoi(rangeStr.substr(separatorPos + 1));

			if (minEmptyCells < 20 || minEmptyCells > 55 ||
				maxEmptyCells < 20 || maxEmptyCells > 55 || minEmptyCells > maxEmptyCells) {
				cout << "挖空的数量范围应在" << 20 << "到" << 55 << "之间，并且最小值不应大于最大值！" << endl;
				return 1;
			}
		}

		if (options.count("-u")) {
			unique = true;
		}

		generatePuzzles(numGames, difficulty, minEmptyCells, maxEmptyCells, unique);
		cout << numGames << " 个数独游戏已生成至 game.txt！" << endl;
	}
	else {
		cout << "无效的选项！" << endl;
		return 1;
	}

	return 0;
}

int row[9];
int col[9];
int grid[9];

//// 打印数独棋盘
//void printBoard(vector<vector<int>>& board) {
//	for (int row = 0; row < BOARD_SIZE; row++) {
//		for (int col = 0; col < BOARD_SIZE; col++) {
//			if (board[row][col] == 0) {
//				cout << "$ ";
//			}
//			else {
//				cout << board[row][col] << " ";
//			}
//		}
//		cout << endl;
//	}
//	cout << endl;
//}

inline int g(int x, int y) {
	return ((x / 3) * 3) + (y / 3);
}

void flip(int x, int y, int z) {//对该位置填z后的回溯和标记(xor) 
	//未标记->标记->未标记(xor的可逆性) 
	row[x] ^= 1 << z;//1<<z=pow(2,z)
	col[y] ^= 1 << z;
	grid[g(x, y)] ^= 1 << z;
}

bool dfs(vector<vector<int>>& board) {
	int temp = BOARD_SIZE + 1, x = -1, y = -1;

	for (int i = 0; i < BOARD_SIZE; ++i) {
		for (int j = 0; j < BOARD_SIZE; ++j) {
			if (board[i][j])	continue;
			int val = row[i] & col[j] & grid[g(i, j)];//该位置上可以填的数的个数
			if (!val)	return false;//1个也不能填，回溯
			if (temp > cnt[val]) {//temp取当前位置可以填的最少的数的个数，并记录下这个位置
				temp = cnt[val];
				x = i; y = j;
			}
		}
	}

	if (x == -1 && y == -1) return true;

	//(x,y)可以填的数的个数
	int val = row[x] & col[y] & grid[g(x, y)];
	for (; val; val -= val & (-val)) {
		int z = num[val & (-val)];
		board[x][y] = z + 1; //之所以加1与二进制标记数组的定义有关 
		/*printBoard(board);*/
		flip(x, y, z);
		if (dfs(board))	return true;
		board[x][y] = 0;
		flip(x, y, z);
	}
	return false;//无解，返回上一层 
}

void dfs1(vector<vector<int>>& board, int& ans) {

	if (ans == 2)
		return;

	int temp = BOARD_SIZE + 1, x = -1, y = -1;

	for (int i = 0; i < BOARD_SIZE; ++i) {
		for (int j = 0; j < BOARD_SIZE; ++j) {
			if (board[i][j])	continue;
			int val = row[i] & col[j] & grid[g(i, j)];//该位置上可以填的数的个数
			if (!val)	return;     // 1个也不能填，回溯
			if (temp > cnt[val]) {	// temp取当前位置可以填的最少的数的个数，并记录下这个位置
				temp = cnt[val];
				x = i; y = j;
			}
		}
	}

	if (x == -1 && y == -1) {
		ans++;
		return;
	}

	//(x,y)可以填的数的个数
	int val = row[x] & col[y] & grid[g(x, y)];
	for (; val; val -= val & (-val)) {
		int z = num[val & (-val)];
		board[x][y] = z + 1; //之所以加1与二进制标记数组的定义有关 
		flip(x, y, z);
		dfs1(board, ans);
		if (ans == 2)
			return;
		board[x][y] = 0;
		flip(x, y, z);
	}
	return;//无解，返回上一层 
}

// 读取数独游戏函数
bool readBoard(ifstream& file, vector<vector<int>>& board) {
	if (file.eof()) {
		return false;
	}

	for (int i = 0; i < BOARD_SIZE; ++i) {
		for (int j = 0; j < BOARD_SIZE; ++j) {
			/*cout << i << " " << j << endl;*/
			char ch;
			if (file >> ch) {
				if (ch == '$')
					board[i][j] = 0;
				else
					board[i][j] = ch - '0';

				/*file >> ch;*/
			}
			else {
				/*cerr << "无法读取数独游戏数据。" << endl;*/
				return false;
			}
		}
		/*char ch;
		file >> ch;*/
	}
	/*char ch;
	file >> ch;*/

	/*printBoard(board);*/

	return true;
}


// 解数独，如果有多个解只返回一个解
bool solvePuzzles(string inputFilePath) {

	ifstream inputFile(inputFilePath);

	vector<vector<int>> board(BOARD_SIZE, vector<int>(BOARD_SIZE));

	/*int cur_cnt = 0;*/
	while (readBoard(inputFile, board))
	{
		/*cout << cur_cnt << endl;
		cur_cnt++;*/

		/*printBoard(board);*/

		for (int i = 0; i < BOARD_SIZE; ++i) {
			//初始化行，列，九宫格标记数组
			//每个数都可以填 
			row[i] = col[i] = grid[i] = (1 << BOARD_SIZE) - 1;
		}
		for (int i = 0; i < BOARD_SIZE; ++i) {
			for (int j = 0; j < BOARD_SIZE; ++j) {
				if (board[i][j])
					flip(i, j, board[i][j] - 1);
			}
		}
		if (!dfs(board))
		{
			cerr << "无解" << endl;
			inputFile.close();
			return false;
		}
		writeBoardToFile(board, "solution.txt");
	}

	inputFile.close();
	return true;
}

bool checkUnique(vector<vector<int>>& board) {

	for (int i = 0; i < BOARD_SIZE; ++i) {
		//初始化行，列，九宫格标记数组
		//每个数都可以填 
		row[i] = col[i] = grid[i] = (1 << BOARD_SIZE) - 1;
	}

	for (int i = 0; i < BOARD_SIZE; ++i) {
		for (int j = 0; j < BOARD_SIZE; ++j) {
			if (board[i][j])
				flip(i, j, board[i][j] - 1);
		}
	}

	int ans = 0;

	dfs1(board, ans);
	return ans == 1;
}

// 将数独棋盘追加写入文件
void writeBoardToFile(vector<vector<int>>& board, const string& filePath) {
	ofstream outputFile(filePath, ios::app);

	if (!outputFile) {
		cout << "无法打开文件 " << filePath << " 进行写入！" << endl;
		return;
	}

	for (int row = 0; row < BOARD_SIZE; row++) {
		for (int col = 0; col < BOARD_SIZE; col++) {
			if (board[row][col] == 0) {
				outputFile << "$ ";
			}
			else
				outputFile << (char)(board[row][col] + '0') << " ";
		}
		outputFile << endl;
	}
	outputFile << endl;

	outputFile.close();
}


// 生成指定数量的数独终局并写入文件 最大数量：9!*3!*3! = 13,063,680 > 1,000,000
void generateFinalBoards(int numBoards) {
	random_device rd;
	mt19937 gen(rd());
	int first_line[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	shuffle(first_line, first_line + 9, gen);

	while (true) {
		int shift[9] = { 0, 3, 6, 1, 4, 7, 2, 5, 8 };

		vector<vector<int>> board(BOARD_SIZE, vector<int>(BOARD_SIZE));

		for (int i = 0; i < 3; i++) {
			vector<int> shiftedVec;
			rotate_copy(first_line, first_line + shift[i], first_line + 9, back_inserter(shiftedVec));
			board[i] = shiftedVec;
		}

		int shift_i1[3] = { 0, 1, 2 };
		do {
			for (int i1 = 3; i1 < 6; i1++) {
				vector<int> shiftedVec;
				rotate_copy(first_line, first_line + shift[3 + shift_i1[i1 - 3]], first_line + 9, back_inserter(shiftedVec));
				board[i1] = shiftedVec;
			}
			int shift_i2[3] = { 0, 1, 2 };
			do {
				for (int i2 = 6; i2 < BOARD_SIZE; i2++) {
					vector<int> shiftedVec;
					rotate_copy(first_line, first_line + shift[6 + shift_i2[i2 - 6]], first_line + 9, back_inserter(shiftedVec));
					board[i2] = shiftedVec;
				}

				writeBoardToFile(board, "finalboards.txt");
				numBoards--;
				if (!numBoards)
					return;

			} while (next_permutation(shift_i2, shift_i2 + 3));

		} while (next_permutation(shift_i1, shift_i1 + 3));

		if (board[0] == vector<int>{9, 8, 7, 6, 5, 4, 3, 2, 1, 0})
			for (int i = 0; i < BOARD_SIZE; i++)
				first_line[i] = i;
		else
			next_permutation(first_line, first_line + 9);
	}
}

// 生成指定数量的数独游戏并写入文件
void generatePuzzles(int numGames, int difficulty, int min_numEmptyCells, int max_numEmptyCells, bool uniqueSolution) {

	generateFinalBoards(numGames);

	ifstream inputFile("finalboards.txt");

	int count = 0;
	while (count < numGames) {
		bool success = false;
		vector<vector<int>> board(BOARD_SIZE, vector<int>(BOARD_SIZE));
		readBoard(inputFile, board);

		while (!success) {
			// 以挖孔数量来衡量难度
			int d = (max_numEmptyCells - min_numEmptyCells) / 3;
			min_numEmptyCells += (difficulty - 1) * d;
			max_numEmptyCells -= (3 - difficulty) * d;


			// 先掏空3*3*2个
			int base[9] = { 0,3,6,27,30,33,54,57,60 };
			int plus[9] = { 0,1,2,9,10,11,18,19,20 };
			for (int k = 0; k < BOARD_SIZE; k++)//每个3*3随机掏空2个
			{
				int i, j,
					hole[2];//3*3里面掏的位置
				hole[0] = rand() % 9;
				hole[1] = rand() % 9;
				while (hole[0] == hole[1])//防止重复
				{
					hole[1] = rand() % 9;
				}
				for (int t = 0; t < 2; t++)
				{
					int dot;
					dot = base[k] + plus[hole[t]];
					i = dot / 9;
					j = dot % 9;
					board[i][j] = 0;
				}
			}

			// 再掏
			int others = min_numEmptyCells - 18 + rand() % (max_numEmptyCells - min_numEmptyCells + 1);
			while (others--)
			{
				int k = rand() % 81;
				int i = k / 9;
				int j = k % 9;

				if (board[i][j] != 0) board[i][j] = 0;
				else others++;
			}

			if (uniqueSolution) {
				// 检查解是否唯一
				vector<vector<int>> copyBoard(board);
				if (checkUnique(copyBoard)) {
					count++;
					writeBoardToFile(board, "game.txt");
					success = true;
				}
			}
			else {
				count++;
				writeBoardToFile(board, "game.txt");
				success = true;
			}
		}
	}

	inputFile.close();
}